﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStruct
{
    /// <summary>
    /// 数组实现的堆栈 顺序栈
    /// </summary>
    internal class Stack
    {
        int[] dataArr;//存放堆栈的数组
        int top = -1;//栈顶指针
        int size;//栈容量 其实就是dataArr的长度
        public Stack(int size)
        {
            dataArr = new int[size];
            this.size = size;
        }

        /// <summary>
        /// 入栈
        /// </summary>
        /// <param name="data"></param>
        public void Push(int data)
        {
            //栈满 扩容
            if (top == (size - 1))
            {
                int[] newData = new int[size * 2];
                for (int i = 0; i < size; i++)
                {
                    newData[i] = this.dataArr[i];
                }
                this.dataArr = newData;
                size = size * 2;
            }
            //赋值 栈顶指针后移
            dataArr[++top] = data;
        }

        /// <summary>
        /// 出栈
        /// </summary>
        /// <returns></returns>
        public int Pop()
        {
            if (top == -1)
            {
                throw new Exception("栈空了!");
            }
            return dataArr[top--];
        }

        /// <summary>
        /// 是否为空栈
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return top == -1;
        }

        /// <summary>
        /// 栈是否满了
        /// </summary>
        /// <returns></returns>
        public bool IsFull()
        {
            return top == (size - 1);
        }

        /// <summary>
        /// 打印栈中的所有元素
        /// </summary>
        public void Print()
        {
            for (int i = 0; i <= top; i++)
            {
                Console.Write(dataArr[i] + " ");
            }
            int bottomNum = 0;
            int topNum = 0;
            if (top >= 0)
            {
                bottomNum = dataArr[0];
                topNum = dataArr[top];
            }

            Console.WriteLine($"栈底:{bottomNum},栈顶:{topNum} 堆栈长度:{GetLength()}");
        }

        public int GetLength()
        {
            return top + 1;
        }

        /// <summary>
        /// 获取栈顶元素 只返回栈顶元素，不出栈
        /// </summary>
        /// <returns></returns>
        public int Peek()
        {
            if (top == -1)
            {
                throw new Exception("空栈！");
            }
            return dataArr[top];
        }
    }
    internal class Stack2
    {
        int[] dataArr;//存放堆栈的数组
        int top = 0;//栈顶指针
        int size;//栈容量 其实就是dataArr的长度
    }
}
